home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
TeX 1995 July
/
TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO
/
graphics
/
pictex
/
tree.sty
< prev
Wrap
Text File
|
1992-08-30
|
11KB
|
354 lines
% Binary tree drawing in LaTeX using the PiCTeX macros.
%
% Edward M. Reingold (reingold@cs.uiuc.edu)
% Nachum Dershowitz (nachum@cs.uiuc.edu)
%
\typeout{Binary Tree Macros. Released 18 Jan 1991; modified 2 Apr 1992.}
%
% These macros are in the public domain. You may use them and copy them at
% will, provided you retain the authorship information.
%
%
% USAGE: \tree[optional root symbol]{left subtree}{right subtree}
%
% For example,
%
% \tree[X]
% {\setdots\tree[Z]
% {\setsolid\tree[Y]{a}{}}
% {\setsolid\tree{c}{d}}}
% {\tree
% {\tree{}{f}}
% {\tree{g}{h}}}
%
% The root symbol and leaves can be anything you can construct in LaTeX
% or PiCTeX. The trees constructed can be used in any context in LaTeX
% or PiCTeX. That is, you can have, say, tables of trees of equations.
%
%
% WARNING: Do not use the tilde (~) as the first character in any subtree!
%
%
% PARAMETERS: Feel free to change the following tree drawing parameters;
% these parameters can be reset even in the middle of a tree.
%
\newdimen\subtreesep \subtreesep=10pt % Distance between nonempty subtrees
\newdimen\levelsep \levelsep=30pt % Distance between successive levels
\def\nodesymbol{$\bullet$} % Default symbol for an internal node
% Tree edges connecting to the default node symbol
% will go to it's center. Other tree edges will be
% chopped off at a node's bounding box.
%
%
% Here's an example that changes the parameters in the middle of the tree:
%
% \subtreesep=15pt\levelsep=40pt
% \tree[\fbox{\subtreesep=5pt\levelsep=13pt\tree[o]{a}{a}}]
% {b}{b}
%
%
% You can get triangular subtrees by using \triangle which has the format
%
% \triangle[optional apex label]{width}{height}
%
% For example,
%
% \tree{\triangle[A]{2\subtreesep}{2\levelsep}}
% {\tree{\triangle{\subtreesep}{\levelsep}}
% {\tree{\fbox{}}
% {\fbox{}}}}
%
%
% Don't fiddle with the stuff that follows; it's fairly delicate.
%
% Working variables
%
\catcode`@=11%
\newdimen\halfsubtreesep % half the subtree separation
%
\newdimen\leftwd % width of left subtree
\newdimen\rightwd % width of right subtree
%
\newcount\rootbullet % flag indicating if root is the default bullet
\newdimen\rootwd % width of root
\newdimen\rootht % height of root
\newdimen\rootdp % depth of root
%
\newcount\leftrootbullet % flag indicating if left root is the default bullet
\newdimen\leftrootht % height of left subtree's root
\newdimen\leftrootwd % width of left subtree's root
\newcount\rightrootbullet% flag indicating if right root is the default bullet
\newdimen\rightrootht % height of right subtree's root
\newdimen\rightrootwd % width of right subtree's root
%
\newdimen\@@root % distance of root midpointfrom left edge of tree
\newdimen\leftroot % distance of root midpoint of left subtree
% from left edge of tree
\newdimen\rightroot % distance of root midpoint of right subtree
% from left edge of tree
%
\newcount\leafnode % flag indicating if subtree just placed is a leaf
%
\newdimen\rootxpos % x-cooordinate of the root midpoint
\newdimen\leftrootpos % position of the root of the left subtree
\newdimen\rightrootpos % position of the root of the right subtree
\newdimen\leftpos % position of the NE corner of the left subtree
\newdimen\rightpos % position of the NW corner of the right subtree
%
\newbox\rootnode % the root node, as placed
\newbox\leftsubtree % the left subtree, as placed
\newbox\rightsubtree % the right subtree, as placed
%
\newdimen\xa % (\xa,\ya) = coordinates of the point on the root
\newdimen\ya % node at which to connect the line to a child
\newdimen\xb % (\xb,\yb) = coordinates of the point on the child
\newdimen\yb % at which to connect the line to the parent
%
\let\ifnextchar=\@ifnextchar%
\def\tree{\ignorespaces%
\def\tree{\ifnextchar[{\treey}{\treex}}%
%
\setdimensionmode%
\setlinear%
%
\@ifnextchar[{\treey}{\treex}%
}%
%
\long\def\treex#1#2{\itree{#1}{#2}{\nodesymbol}} % use default node symbol
\long\def\treey[#1]#2#3{\itree{#2}{#3}{#1}} % use specified node symbol
%
\long\def\itree#1#2#3{\ignorespaces % #1=left, #2=right, #3=root
%
\halfsubtreesep=\subtreesep % Do this calculation for each node so its...
\divide\halfsubtreesep by 2 % ...value can vary throughout the tree
%
\ignorespaces%
%
% Recursively draw nonempty left subtree
%
\ifx ~#1~\ignorespaces%
\else%
\leafnode=1 % Assume left subtree is a leaf
\setbox\leftsubtree=\hbox{#1}\ignorespaces
\leftwd=\wd\leftsubtree%
\leftroot=\@@root%
\leftrootbullet=\rootbullet%
\leftrootht=\rootht%
\leftrootwd=\rootwd%
\ifnum \leafnode=1%
\leftroot=\leftwd%
\divide\leftroot by 2%
\leftrootbullet=0%
\leftrootht=\ht\leftsubtree%
\advance\leftrootht by \dp\leftsubtree%
\leftrootwd=\leftwd%
\fi%
\fi%
%
% Recursively draw nonempty right subtree
%
\ifx ~#2~\ignorespaces%
\else%
\leafnode=1 % Assume right subtree is a leaf
\setbox\rightsubtree=\hbox{#2}\ignorespaces%
\rightwd=\wd\rightsubtree%
\rightroot=\@@root%
\rightrootbullet=\rootbullet%
\rightrootht=\rootht%
\rightrootwd=\rootwd%
\ifnum \leafnode=1%
\rightroot=\rightwd%
\divide\rightroot by 2%
\rightrootbullet=0%
\rightrootht=\ht\rightsubtree%
\advance\rightrootht by \dp\rightsubtree%
\rightrootwd=\rightwd%
\fi%
\fi%
%
% In the case of empty subtrees, give artificial values for those empty
% trees so that the later calculations are done properly.
%
\ifx ~#1#2~\ignorespaces % Both subtrees empty
\rightroot=0pt%
\leftroot=-\halfsubtreesep%
\leftwd=-\halfsubtreesep%
\else\ifx ~#1~\ignorespaces % Left subtree empty, right subtree not empty
\leftroot=\rightroot%
\advance\leftroot by -\subtreesep%
\leftwd=-\subtreesep%
\else\ifx ~#2~\ignorespaces % Right subtree empty, left subtree not empty
\rightroot=\leftroot%
\advance\rightroot by -\leftwd%
\fi\fi\fi%
%
% With the subtrees done, now do the root node
%
\setbox\rootnode=\hbox{\setcoordinatemode #3}\ignorespaces%
\global\rootwd=\wd\rootnode%
\global\rootht=\ht\rootnode%
\global\advance\rootht by \dp\rootnode%
\ifx \nodesymbol#3\ignorespaces%
\global\rootbullet=1%
\else\ignorespaces%
\global\rootbullet=0%
\fi%
%
% Find distance of the root midpoint from left edge of the tree
%
\global\@@root=\leftroot%
\global\advance\@@root by \rightroot%
\global\advance\@@root by \leftwd%
\global\advance\@@root by \subtreesep%
\ifdim \@@root<\rootwd \global\@@root=\rootwd \fi%
\global\divide\@@root by 2%
%
% Indicate this root and all its ancestors are not a leaves
%
\global\leafnode=0%
%
% Find positions of the root and those of the roots of the subtrees
%
\leftrootpos=\leftroot%
\advance\leftrootpos by -\leftwd%
\advance\leftrootpos by -\halfsubtreesep%
%
\rightrootpos=\rightroot%
\advance\rightrootpos by \halfsubtreesep%
%
\rootxpos=\leftrootpos%
\advance\rootxpos by \rightrootpos%
\divide\rootxpos by 2%
%
\leftpos=0pt%
\advance\leftpos by \leftrootht%
\divide\leftpos by 2%
%
\rightpos=0pt%
\advance\rightpos by \rightrootht%
\divide\rightpos by 2%
%
% Now the root is a box of width \rootwd and total height \rootht, centered
% at (\rootxpos,\levelsep); the root of the left subtree is a box of
% width \leftrootwd and total height \leftrootht, centered at
% (\leftrootpos,0); the root of the right subtree is a box of width
% \rightrootwd and total height \rightrootht, centered at (\rightrootpos,0).
%
%
\beginpicture
%
\put {\box\rootnode} at {\rootxpos} {\levelsep} % Draw the root
%
\ifx ~#1~\else % Draw the left subtree
\put {\box\leftsubtree} [rt] at {-\halfsubtreesep} {\leftpos}
\xa=\rootxpos%
\ya=\levelsep%
\ifnum\rootbullet=0%
\chop{\rootxpos}{\levelsep}{-\rootwd}{\rootht}{\leftrootpos}{0}%
{\xa}{\ya}%
\fi%
\xb=\leftrootpos%
\yb=0pt%
\ifnum\leftrootbullet=0%
\chop{\leftrootpos}{0}{\leftrootwd}{-\leftrootht}{\rootxpos}{\levelsep}%
{\xb}{\yb}%
\fi%
\plot {\xa} {\ya} {\xb} {\yb} /%
\fi%
%
\ifx ~#2~\else % Draw the right subtree
\put {\box\rightsubtree} [lt] at {\halfsubtreesep} {\rightpos}
\xa=\rootxpos%
\ya=\levelsep%
\ifnum\rootbullet=0%
\chop{\rootxpos}{\levelsep}{\rootwd}{\rootht}{\rightrootpos}{0}%
{\xa}{\ya}%
\fi%
\xb=\rightrootpos%
\yb=0pt%
\ifnum\rightrootbullet=0%
\chop{\rightrootpos}{0}{-\rightrootwd}{-\rightrootht}{\rootxpos}%
{\levelsep}{\xb}{\yb}%
\fi
\plot {\xa} {\ya} {\xb} {\yb} /%
\fi%
%
% Draw the bottom of the triangle, when appropriate.
%
\ifx#1. \ifx#2. \plot {\leftrootpos} {0pt} {\rightrootpos} {0pt} / \fi\fi%
%
\endpicture%
}%
%
\long\def\triangle{\ifnextchar[{\triangley}{\trianglex}}%
\long\def\trianglex#1#2{\itriangle{#1}{#2}{}} % use empty apex symbol
\long\def\triangley[#1]#2#3{\itriangle{#2}{#3}{#1}} % use specified apex symbol
\long\def\itriangle#1#2#3{% A triangle #1 wide and #2 high, #3 at apex
\subtreesep=#1%
\levelsep=#2%
\tree[#3]{.}{.}%
}%
%
\newcount\@@x% Scratch counters used in the computations of \chop
\newcount\@@y% to find the location on the border of a node's bounding
\newcount\@@a% box at which to attach a line aimed at a target point
\newcount\@@b% from the center of the box.
\newcount\@@c%
\newcount\@@d% It would be better to do all these calculation in dimen's
\newcount\@@e% instead of counters, but so many dimen's are used above
\newcount\@@f% that to do so would make running out of dimen's very probable.
\newcount\@@g%
\newcount\@@h% Forgive us for not explaining the following computations;
\newcount\@@l% they're based on elementary analytical geometry.
%
\def\chop#1#2#3#4#5#6#7#8{\ignorespaces%
% (#1,#2) = coordinates of center of bounding box
% #3 x #4 = width x height of bounding box
% (#5,#6) = coordinates of target point
% (#7,#8) = coordinates of computed intersection
% point
%
\@@a=#1\divide \@@a by 10000% Scale down to prevent arithmetic overflow.
\@@b=#2\divide \@@b by 10000%
\@@c=#3\divide \@@c by 10000%
\@@d=#4\divide \@@d by 10000%
\@@e=#5\divide \@@e by 10000%
\@@f=#6\divide \@@f by 10000%
%
\@@l=-\@@f\advance\@@l by \@@b%
%%
\@@y=-\@@d%
\divide \@@y by 2%
\advance\@@y by \@@b%
%%
\@@g=\@@c%
\divide \@@g by 2%
\advance\@@g by \@@a%
%%
\@@x=-\@@a%
\advance\@@x by \@@e%
\multiply\@@x by \@@d%
\divide\@@x by \@@l%
\divide\@@x by 2%
\advance \@@x by \@@a%
%%
\count255=-\@@a%
\advance\count255 by \@@e%
\multiply\count255 by 2%
\@@h=-\@@c%
\multiply \@@h by \@@l%
\divide \@@h by \count255%
\advance \@@h by \@@b%
%
\ifnum #5>#1%
\ifnum\@@x>\@@g\else\@@g=\@@x\@@h=\@@y\fi%
\else%
\ifnum\@@x<\@@g\else\@@g=\@@x\@@h=\@@y\fi%
\fi%
\multiply\@@g by 10000% Scale back up
\multiply\@@h by 10000%
\global#7=\@@g sp%
\global#8=\@@h sp%
}%
\catcode`@=12%